import com.sun.javafx.image.impl.IntArgb;

public class SmallestLengthOfSubarray {
    /*
    * 长度最小的子数组
    * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。
    * 如果不存在符合条件的子数组，返回 0。
    * */

    public static void main(String[] args) {

    }

    // 我的想法1：滑动窗口，从子数组长度为一开始找，在数组上滑动，寻找是否满足条件，没有则窗口长度加1，直至找到
    // 结果是，超时了
    public int mySolution1(int target, int[] nums){
        int head,tail;
        for(int len = 1; len <= nums.length; len++){
            head = 0;
            tail = len-1;
            while(tail < nums.length){
                int sum = 0;
                for(int i = head; i<= tail; i++){
                    sum += nums[i];
                }
                if(sum >= target){
                    return len;
                } else {
                    head++;
                    tail++;
                }
            }
        }
        return 0;
    }

    // 我的想法2：还是滑动窗口，但这次只让窗口头尾从头到尾遍历一遍，窗口长度随时变化，只记录遍历过程中最小的窗口长度
    // 过啦！
    public int mySolution2(int target, int[] nums){
        int head = 0, tail = 0, sum = 0;
        int result = Integer.MAX_VALUE;
        while (tail < nums.length){
            // 窗口尾部向前扩张一格
            sum += nums[tail];
            // 如果和满足条件，窗口头部前进，缩小一格，直至和不满足条件，然后尾部继续扩张
            for(; sum >= target; sum -= nums[head++]){
                int len = tail - head + 1;
                result = len < result? len : result;
            }
            tail++;
        }
        return result == Integer.MAX_VALUE? 0 : result;
    }
}
